package com.qjc.demo.algorithm.斐波那契数列;

/**
 * @ClassName: Fibonacci
 * @Description: 斐波那契数列
 * @Author: qjc
 * @Date: 2022/5/6 9:55 AM
 */
public class Fibonacci {
    // 方法1：递归法实现
    public static int normal(int n) {
        if (n <= 1) {
            return n;
        }
        return normal(n - 1) + normal(n - 2);
    }

    // 方法2：递归分治+备忘录实现
    public static long memory(long[] arr, int n) {
        if (n <= 1) {
            return n;
        }
        if (arr[n] == 0) {
            arr[n] = memory(arr, n - 1) + memory(arr, n - 2);
        }
        return arr[n];
    }

    // 方法3：使用动态规划，DP方程
    public static long dp(int n) {
        if (n <= 1) return n;
        long[] arr = new long[n + 1];
        arr[0] = 0;
        arr[1] = 1;
        for (int i = 2; i <= n; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr[n];
    }

    public static void main(String[] args) {
        System.out.println(normal(10));
        int n = 64;
        System.out.println(memory(new long[n + 1], n));
        System.out.println(dp(n));
    }

}
